package com.turbo.leetcode.example;

import com.turbo.leetcode.example.entity.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 恢复二叉搜索树
 * @see <a href="https://leetcode.cn/problems/recover-binary-search-tree/solutions/365385/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/">leetcode</a>
 */
public class RecoverTree {
    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n3 = new TreeNode(3);
        TreeNode n2 = new TreeNode(6, n1, n3);
        TreeNode n5 = new TreeNode(5);
        TreeNode n4 = new TreeNode(4, n2, n5);
        TreeNode n6 = new TreeNode(2);
        n5.setRight(n6);
        System.out.println(BinaryTreeInorder.inorderTraversal(n4));
        recoverTree(n4);
        System.out.println(BinaryTreeInorder.inorderTraversal(n4));
    }
    /**
     * 方法二：隐式中序遍历<br/>
     * 思路与算法<br/>
     *
     * 方法一是显式地将中序遍历的值序列保存在一个 nums 数组中，然后再去寻找被错误交换的节点，但我们也可以隐式地在中序遍历的过程就找到被错误交换的节点 x 和 y。
     *
     * 具体来说，由于我们只关心中序遍历的值序列中每个相邻的位置的大小关系是否满足条件，且错误交换后最多两个位置不满足条件，因此在中序遍历的过程我们只需要维护当前中序遍历到的最后一个节点 pred，然后在遍历到下一个节点的时候，看两个节点的值是否满足前者小于后者即可，如果不满足说明找到了一个交换的节点，且在找到两次以后就可以终止遍历。
     *
     * 这样我们就可以在中序遍历中直接找到被错误交换的两个节点 x 和 y，不用显式建立 nums 数组。
     *
     * 中序遍历的实现有迭代和递归两种等价的写法，在本方法中提供迭代实现的写法。使用迭代实现中序遍历需要手动维护栈。<br/>
     *
     * 作者：力扣官方题解<br/>
     * 链接：https://leetcode.cn/problems/recover-binary-search-tree/solutions/365385/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/<br/>
     * 来源：力扣（LeetCode）<br/>
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。<br/>
     * @param root
     */
    public static void recoverTree(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode x = null, y = null, pred = null;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.getLeft();
            }
            root = stack.pop();
            if (pred != null && root.getVal() < pred.getVal()) {
                y = root;
                if (x == null) {
                    x = pred;
                } else {
                    break;
                }
            }
            pred = root;
            root = root.getRight();
        }

        swap(x, y);
    }

    public static void swap(TreeNode x, TreeNode y) {
        int tmp = x.getVal();
        x.setVal(y.getVal());
        y.setVal(tmp);
    }
}
